package com.qrpcw.datastructures;

class DoublyNode{
	DoublyNode next;
	DoublyNode prev;
	int data;
	
	public DoublyNode(int data){
		this.data = data;
		next = null;
		prev = null;
	}
}

public class DoublyLinkedList {
	private DoublyNode head;
    private DoublyNode tail;
    
	public DoublyLinkedList() {
		head = null;
		tail = null;
	}

	public DoublyNode search(DoublyLinkedList L, int data){
		DoublyNode x = L.head;
		while(data != x.data && x != null ){
			x = x.next;
		}
		return x;
	}
	
	public void add(DoublyNode newNode){
		if (newNode == null){
			 return;
		}else {
			newNode.next = null;
	        if (head == null) {
	            head = newNode;
	            tail = newNode;
	          } else {
	            newNode.prev = tail;
	            newNode.next = null;
	            tail.next = newNode;
	            tail = newNode;
	          }
	    }
	}
	
	public void delete(DoublyLinkedList L, int data){
		DoublyNode x = L.head;
		while(x.data != data){
			x = x.next;
		}
		x.prev.next = x.next;
		x.next.prev = x.prev;
	}
	
	public void insert(DoublyLinkedList L, DoublyNode newNode){
		newNode.prev = null;
		newNode.next = L.head;
		L.head.prev = newNode;
		L.head = newNode;
	}
	
	public void TraversalPrint(DoublyLinkedList L){
		DoublyNode x = L.head;
		while(x != null){
			System.out.print(x.data);
			x = x.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		DoublyLinkedList test = new DoublyLinkedList();
		DoublyNode[] nodes = new DoublyNode[10];
		test.add(nodes[0]=new DoublyNode(1));
		test.add(nodes[1]=new DoublyNode(2));
		test.add(nodes[2]=new DoublyNode(3));
		test.add(nodes[3]=new DoublyNode(4));
		test.add(nodes[4]=new DoublyNode(6));
		test.add(nodes[5]=new DoublyNode(7));
		test.TraversalPrint(test);
		test.delete(test, 3);
		test.TraversalPrint(test);
		test.insert(test, nodes[6]=new DoublyNode(88));
		test.TraversalPrint(test);
	}
}
